package C055;

/**
 * ClassName: C02
 * Package: C055
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/10 14:46
 * @Version 1.0
 * @Since 1.0
 */
public class C02 {
    public static void main(String[] args) {
        int[][] arr = {{1,3},{2,0},{5,10},{6,-10}};
        System.out.println(findMaxValueOfEquation(arr, 1));
    }
    /*
    2 <= points.length <= 10^5
    points[i].length == 2
    -10^8 <= points[i][0], points[i][1] <= 10^8
    0 <= k <= 2 * 10^8
    对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。
     */

    static int MAXLEN = 100001;
    static int[][] deque = new int[MAXLEN][2];
    static int h, t, n;

    public static int findMaxValueOfEquation(int[][] points, int k) {
        n = points.length;
        h = t = 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // 头删除
            while (h < t && (points[i][0] - deque[h][0] > k)) {
                h++;
            }
            if(h < t) {
                ans = Math.max(ans, points[i][0] + points[i][1] + deque[h][1] - deque[h][0]);
            }

            // 尾删除
            while (h < t && (points[i][1] - points[i][0]) >= (deque[t - 1][1] - deque[t - 1][0])) {
                t--;
            }
            deque[t][0] = points[i][0];
            deque[t++][1] = points[i][1];
        }
        return ans;
    }
}
